package bst

import (
	"errors"
	"fmt"
)

var (
	ErrNodeNotFound = errors.New("node node found")
)

// Node 二叉树 -> 二分搜索树
type Node struct {
	value       int
	left, right *Node
}

// Add 二叉树添加
func (n *Node) Add(value int) {
	if n == nil {
		fmt.Println("add value to nil node")
		return
	}
	// 往 n 为根节点的树上添加
	add(n, value)
}
func add(head *Node, value int) *Node {
	if head == nil {
		return CreateNode(value, nil, nil)
	}
	switch {
	case value < head.value:
		head.left = add(head.left, value)
	case value > head.value:
		head.right = add(head.right, value)
	case value == head.value:
		// nothing to do  这里的bst定义不存储重复元素，可以在节点中添加
	}
	return head
}

// Contains 二叉树判断
func (n *Node) Contains(value int) bool {
	return contains(n, value)
}
func contains(node *Node, value int) bool {
	if node == nil { // 递归结束条件一：递归到底
		return false
	}

	switch {
	case value < node.value:
		return contains(node.left, value)
	case value > node.value:
		return contains(node.right, value)
	case value == node.value:
		return true // 递归找到目标元素
	}
	return false
}

// Maximum 二叉树查找最大最小值
func (n *Node) Maximum() (int, error) {
	node, err := maximum(n)
	if err != nil {
		return -1, err
	}
	return node.value, nil
}

func maximum(node *Node) (*Node, error) {
	if node == nil {
		return &Node{}, ErrNodeNotFound
	}
	if node.right == nil {
		return node, nil
	}
	return maximum(node.right)
}

func (n *Node) Minimum() (int, error) {
	node, err := minimum(n)
	if err != nil {
		return -1, err
	}
	return node.value, nil
}

func minimum(node *Node) (*Node, error) {
	if node == nil {
		return &Node{}, ErrNodeNotFound
	}

	if node.left == nil {
		return node, nil
	}
	return minimum(node.left)
}

// Size 二叉树信息
func (n *Node) Size() int {
	if n == nil {
		return 0
	}

	nodes := n.TraversalWithChan()
	nodeCount := 0
	for _ = range nodes {
		nodeCount++
	}
	return nodeCount
}

func (n *Node) IsEmpty() bool {
	return n.Size() == 0
}

// RemoveMax 二叉树删除最大最小值
func (n *Node) RemoveMax() (int, error) {
	value, err := n.Maximum() // 查找到最大值是多少
	if err != nil {
		return -1, err
	}
	_ = removeMax(n)
	return value, nil
}

func removeMax(node *Node) *Node {
	if node.right == nil {
		left := node.left
		node.left = nil
		return left
	}
	node.right = removeMax(node.right)
	return node
}

func (n *Node) RemoveMin() (int, error) {
	value, err := n.Minimum()
	if err != nil {
		return -1, err
	}
	_ = removeMin(n)
	return value, nil
}

func removeMin(node *Node) *Node {
	if node.left == nil {
		right := node.right
		node.right = nil
		return right
	}
	node.left = removeMin(node.left)
	return node
}

// Remove 二叉树删除任意值
func (n *Node) Remove(value int) error {
	_, err := remove(n, value)
	if err != nil {
		return err
	}
	return nil
}

// TODO 这个函数目前有问题
func remove(node *Node, value int) (*Node, error) {
	if node == nil {
		return nil, ErrNodeNotFound
	}

	switch {
	case value < node.value:
		return remove(node.left, value)
	case value > node.value:
		return remove(node.right, value)
	default:

		if node.left == nil {
			right := node.right
			node.right = nil
			return right, nil
		}

		if node.right == nil {
			left := node.left
			node.left = nil
			return left, nil
		}

		// 左子树， 右子树都不为空， hibard deletion
		successor, _ := minimum(node.right) // 后继删除
		successor.left = node.left
		successor.right = removeMin(node.right)
		node.left = nil
		node.right = nil
		return successor, nil
	}

}

// floor ceil
// rank  select

// CreateNode 创建二叉树节点
func CreateNode(value int, left, right *Node) *Node {
	return &Node{value, left, right}
}
